package lib

func init() {
	Probs = append(Probs, Problem{
		Num:         135,
		Discription: "分糖果：每个孩子至少一个糖果，评分高的孩子的糖果要比评分少的孩子多，返回最少糖果总数",
		Level:       3,
		Labels: map[string]int{
			"贪心": 1,
		},
	})
}

//为了尽可能地减少糖果数，降序和升序数组中，每个元素的值都是连续的
func Candy(ratings []int) int {
    //降序子数组的第一个位置的糖果数
	firstDec := 0
    //升序子数组最后一个位置的糖果数
	lastInc := 1
	num := 1
	for i := 1; i < len(ratings); i++ {
        //和前一个孩子评分相等，视为一个新的升序数组的开始
		if ratings[i] == ratings[i-1] {
			num += 1
			lastInc = 1
			firstDec = 0
			continue
		}

		if ratings[i] > ratings[i-1] {
			if firstDec != 0 {
                //降序数组的结束
				lastInc = 2
				firstDec = 0
			} else {
                //升序数组的延续
				lastInc++
			}
			num += lastInc
		} else {
            //降序数组的延续或升序数组的结束
			firstDec++
			num += firstDec
            //如果升序数组的最后一个孩子的糖果数和降序数组的第一个孩子的糖果数相同，需要把升序数组的最后一个孩子并入降序数组
			if firstDec == lastInc {
				firstDec++
				num += 1
			}
		}
	}

	return num
}
